/**
 * @version Create on 2012-10-29
 * @author Yinzi Chen
 */

public class BalancedBinaryTree {

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	boolean isBalanced;

	public int search(TreeNode root, int dep) {
		if (!isBalanced)
			return dep;
		int h1 = dep, h2 = dep;
		if (root.left != null) {
			h1 = search(root.left, dep + 1);
		}
		if (root.right != null) {
			h2 = search(root.right, dep + 1);
		}
		if (Math.abs(h1 - h2) > 1)
			isBalanced = false;
		return Math.max(h1, h2);

	}

	public boolean isBalanced(TreeNode root) {
		if (root == null)
			return true;
		isBalanced = true;
		search(root, 0);
		return isBalanced;
	}

	public static void main(String[] args) {

	}

}
